package zw_1_100.zw_4_寻找两个正序数组的中位数;

class Solution {

    public static void main(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4};
        double v = findMedianSortedArrays(nums1, nums2);
        System.out.println(v);
    }


    /**
     * 解法四：二分，对数组切片
     * 时间复杂度：我们对较短的数组进行了二分查找，所以时间复杂度是 O(log（min（m，n））。
     * 空间复杂度：只有一些固定的变量，和数组长度无关，所以空间复杂度是O(1)。
     *
     * @param A
     * @param B
     * @return
     */
    public static double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) {
            return findMedianSortedArrays(B, A); // 保证 m <= n
        }
        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j != 0 && i != m && B[j - 1] > A[i]) { // i 需要增大
                iMin = i + 1;
            } else if (i != 0 && j != n && A[i - 1] > B[j]) { // i 需要减小
                iMax = i - 1;
            } else { // 达到要求，并且将边界条件列出来单独考虑
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[j - 1];
                } else if (j == 0) {
                    maxLeft = A[i - 1];
                } else {
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                } // 奇数的话不需要考虑右半部分

                int minRight = 0;
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(B[j], A[i]);
                }

                return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
            }
        }
        return 0.0;
    }


    /**
     * 解法三
     * 时间复杂度：每进行一次循环，我们就减少 k/2 个元素，所以时间复杂度是 O(log(k))，而 k=(m+n)/2，所以最终的复杂也就是 O(log(m+n))。
     * 空间复杂度：虽然我们用到了递归，但是可以看到这个递归属于尾递归，所以编译器不需要不停地堆栈，所以空间复杂度为 O(1)。
     *
     * @param nums1
     * @param nums2
     * @return
     */
//    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
//        int n = nums1.length;
//        int m = nums2.length;
//        //因为数组是从索引0开始的，因此我们在这里必须+1，即索引(k+1)的数，才是第k个数。
//        int left = (n + m + 1) / 2;
//        int right = (n + m + 2) / 2;
//        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k
//        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
//    }
//    private static int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
//        //因为索引和算数不同6-0=6，但是是有7个数的，因为end初始就是数组长度-1构成的。
//        //最后len代表当前数组(也可能是经过递归排除后的数组)，符合当前条件的元素的个数
//        int len1 = end1 - start1 + 1;
//        int len2 = end2 - start2 + 1;
//        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
//        //就是如果len1长度小于len2，把getKth()中参数互换位置，即原来的len2就变成了len1，即len1，永远比len2小
//        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
//        //如果一个数组中没有了元素，那么即从剩余数组nums2的其实start2开始加k再-1.
//        //因为k代表个数，而不是索引，那么从nums2后再找k个数，那个就是start2 + k-1索引处就行了。因为还包含nums2[start2]也是一个数。因为它在上次迭代时并没有被排除
//        if (len1 == 0) return nums2[start2 + k - 1];
//
//        //如果k=1，表明最接近中位数了，即两个数组中start索引处，谁的值小，中位数就是谁(start索引之前表示经过迭代已经被排出的不合格的元素，即数组没被抛弃的逻辑上的范围是nums[start]--->nums[end])。
//        if (k == 1) return Math.min(nums1[start1], nums2[start2]);
//
//        //为了防止数组长度小于 k/2,每次比较都会从当前数组所生长度和k/2作比较，取其中的小的(如果取大的，数组就会越界)
//        //然后数组如果len1小于k / 2，表示数组经过下一次遍历就会到末尾，然后后面就会在那个剩余的数组中寻找中位数
//        int i = start1 + Math.min(len1, k / 2) - 1;
//        int j = start2 + Math.min(len2, k / 2) - 1;
//
//        //如果nums1[i] > nums2[j]，表示nums2数组中包含j索引，之前的元素，逻辑上全部淘汰，即下次从J+1开始。
//        //而k则变为k - (j - start2 + 1)，即减去逻辑上排出的元素的个数(要加1，因为索引相减，相对于实际排除的时要少一个的)
//        if (nums1[i] > nums2[j]) {
//            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
//        } else {
//            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
//        }
//    }


    /**
     * 解法二
     * 不需要将两个数组合并，只需要找到中位数可以
     * 时间复杂度：遍历 len/2+1 次，len=m+n，所以时间复杂度依旧是 O(m+n)。
     * 空间复杂度：我们申请了常数个变量，也就是 m，n，len，left，right，aStart，bStart 以及 i。
     * 总共 8 个变量，所以空间复杂度是 O(1）。
     *
     * @param A
     * @param B
     * @return
     */
//    public static double findMedianSortedArrays(int[] A, int[] B) {
//        int m = A.length;
//        int n = B.length;
//        int len = m + n;
//        int left = -1, right = -1;
//        int aStart = 0, bStart = 0;
//        for (int i = 0; i <= len / 2; i++) {
//            left = right;
//            if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
//                right = A[aStart++];
//            } else {
//                right = B[bStart++];
//            }
//        }
//        if ((len & 1) == 0)
//            return (left + right) / 2.0;
//        else
//            return right;
//    }


    /**
     * 解法一
     * 先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。
     * 时间复杂度：遍历全部数组 (m+n)
     * 空间复杂度：开辟了一个数组，保存合并后的两个数组 O(m+n)
     * @param nums1
     * @param nums2
     * @return
     */
//    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
//        //合并两个数组
//        int len1 = nums1.length;
//        int len2 = nums2.length;
//        int[] nums = new int[len1 + len2];
//        int count = 0;
//        int i = 0, j = 0;
//        while (count < (len1 + len2)) {
//            if (i == len1) {
//                while (j != len2) {
//                    nums[count++] = nums2[j++];
//                }
//                break;
//            }
//            if (j == len2) {
//                while (i != len1) {
//                    nums[count++] = nums1[i++];
//                }
//                break;
//            }
//            if (nums1[i] < nums2[j]) {
//                nums[count++] = nums1[i++];
//            } else {
//                nums[count++] = nums2[j++];
//            }
//        }
//        //找到中位数
//        double res = count % 2 == 0 ? (nums[count / 2] + nums[count / 2 - 1]) / 2.0 : nums[count / 2];
//        return res;
//    }
}
